package com.yuan.algorithms.算法导论_第一部分;

/**
 * @author YouYuan
 * <br>E-mail:1265161633@qq.com
 * <br>创建时间：2015年11月12日 下午9:22:13
 * <br>说明:插入排序的实现
 */
public class InsertionSort {

	public static void main(String[] args) {
		double[] a = {5, 2, 4, 6, 1, 3};
		double[] b = {5, 2, 4, 6, 1, 3};
		insertionSort(a); 
		for(double data : a) {
			System.out.print(data+" ");
		}
		System.out.println();
		desInsertSort(b);
		for(double data : b) {
			System.out.print(data+" ");
		}
		System.out.println();
	}

	/**
	 * 插入排序的降序排列
	 * @param b
	 */
	private static void desInsertSort(double[] b) {
		for (int i = 1; i < b.length; i++) {
			double key = b[i];
			int j = i - 1;
			while(j >= 0 && key > b[j]) {
				b[j+1] = b[j];
				--j;
			}
			b[j+1] = key;
		}
	}

	private static void insertionSort(double[] arr) {
		for (int i = 1; i < arr.length; i++) {
			double key = arr[i];//当前需要插入的值
			int j = i - 1;//从其前一位开始比较
			while(j >= 0 && arr[j] > key) {
				arr[j+1] = arr[j];//如果当前元素比要插入的元素大，则将当前元素后移
				--j;//继续向前查找比key大的元素
			}
			arr[j+1] = key;//将key插入到对应的位置
		}
	}

}
